#ifndef SORTING_ALGO_H
#define SORTING_ALGO_H

#include <vector>
#include <iostream>
#include <algorithm>

class SORTING {
    public:
    // 选择排序
    void selectionSort(std::vector<int> &nums);

    // 冒泡排序
    void bubbleSort(std::vector<int> &nums);

    // 冒泡排序标志优化
    void bubbleSortWithFlag(std::vector<int> &nums);

    // 插入排序
    void insertionSort(std::vector<int> &nums);

    // 快速排序
    void quickSort(std::vector<int> &nums,int left,int right);

    // 快速排序 尾递归优化
    void quickSortTail(std::vector<int> &nums,int left,int right);

    // 归并排序
    void mergeSort(std::vector<int> &nums,int left,int right);

    // 堆排序
    void heapSort(std::vector<int> &nums);

    // 桶排序
    void bucketSort(std::vector<float> &nums);

    // 计数排序，简单实现，无法用于排序对象
    void countingSortNaive(std::vector<int> &nums);

    // 计数排序，完整实现，可用于排序对象，并且是稳定排序
    void countingSort(std::vector<int> &nums);

    // 基数排序
    void radixSort(std::vector<int> &nums);
    
    private:

    // 交换函数
    bool mySwap(std::vector<int> &nums,int i,int j);

    // 快速排序的哨兵划分
    int partition(std::vector<int> &nums,int left,int right);

    // 快速排序优化，选取三个元素的中位数
    int medianThree(std::vector<int> &nums,int left,int mid,int right);

    // 哨兵划分，中位数优化
    int partionWithMed(std::vector<int> &nums,int left,int right);

    // 归并排序的合并左右子数组函数
    void merge(std::vector<int> &nums,int left,int mid,int right);

    // 堆排序辅助函数，堆长度为n，从节点i开始，顶至底堆化 
    void siftDown(std::vector<int> &nums,int n,int i);

    // 最大值函数，返回两个输入的最大值
    inline int max(int a,int b) {
        return a > b ? a : b;
    }

    // 获取元素num的第k位，其中exp = 10^(k-1)
    inline int digit(int num,int exp) {
        // 传入exp而非k可以避免在此重复执行昂贵的次方计算
        return (num / exp ) % 10;
    }

    // 辅助进行基数排序的计数排序
    // 根据nums第k位排序
    void countingSortDigit(std::vector<int> &nums,int exp);


};

#endif // sorting_algo.h